#include <cstdlib>
#include <vector>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
private:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder, int& pos, int l, int r) {
        if (pos >= preorder.size() || l > r) {
            return nullptr;
        }
        int mid_i;
        TreeNode* node = new TreeNode(preorder[pos]);
        for (int i = l; i <= r; i++) {
            if (inorder[i] == preorder[pos]) {
                mid_i = i;
                break;
            }
        }
        pos++;
        node->left = buildTree(preorder, inorder, pos, l, mid_i - 1);
        node->right = buildTree(preorder, inorder, pos, mid_i + 1, r);
        return node;
    }
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int pos = 0;
        return buildTree(preorder, inorder, pos, 0, preorder.size() - 1);
    }
};